#ifndef MERGE_SORT
#define MERGE_SORT
template<class Type,int Length>
void MergeSort(Type (&array) [Length] ){
	Type * tempArray = new Type [ Length ];      // need extra O(n) space
	 MergeSort(array , tempArray , 0 , Length - 1);
	delete [] tempArray;
}
template<class Type>
void MergeSort(Type array[] , Type tempArray [] ,int start , int end){
	if(start >= end)return;
	int middle = (start + end) / 2;

	MergeSort(array , tempArray , start , middle);
	MergeSort(array , tempArray , middle +1 , end);

	// merging 
	int s1 = start , s2 = middle+1 , index = start;
	while ( s1 <= middle && s2 <= end ){
		if( array[s1] < array[s2] )
			tempArray[index++] = array[s1++];		
		else		
			tempArray[index++] = array[s2++];		
	}
	while(s1 <= middle ) 	tempArray[index++] = array[s1++];	
	while(s2 <= end )	 tempArray[index++] = array[s2++];
	
	//copying
	for(int i = start ; i <= end ; ++i)
		array[i] = tempArray[i];
}
#endif